package listnode;

public class _147_对链表进行插入排序 {

    /**
     * 对链表进行插入排序。
     * 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
     * <p>
     *  
     * <p>
     * 插入排序算法：
     * <p>
     * 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
     * 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
     * 重复直到所有输入数据插入完为止。
     * <p>
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/insertion-sort-list
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param head
     * @return
     */
    public static ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode order = new ListNode(head.val);
        head = head.next;

        ListNode orderHead = order;
        ListNode cur = order;
        while (head != null) {
            ListNode pre = null;
            while (cur != null) {
                if (head.val > cur.val) {
                    ListNode next = cur.next;
                    if (next == null) {
                        cur.next = new ListNode(head.val);
                        break;
                    } else if (next.val > head.val) {
                        ListNode newNode = new ListNode(head.val);
                        cur.next = newNode;
                        newNode.next = next;
                        break;
                    } else {
                        pre = cur;
                        cur = cur.next;
                    }
                } else {
                    ListNode newNode = new ListNode(head.val);
                    newNode.next = cur;
                    if (pre != null) {
                        pre.next = newNode;
                    } else {
                        orderHead = newNode;
                    }
                    break;
                }
            }
            cur = orderHead;
            head = head.next;
        }
        return cur;
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode(-1);
        ListNode n2 = new ListNode(5);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(0);
        ListNode n6 = new ListNode(3);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        ListNode node = insertionSortList(n1);
    }

    public ListNode insertionSortList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        ListNode pre = head;
        ListNode cur = head.next;
        dummy.next = head;
        while (cur != null) {
            if (pre.val <= cur.val) {// 本来就有序
                pre = cur;
                cur = cur.next;
            } else {
                ListNode p = dummy;
                // 找到一个位置使得p < cur < p.next
                while (p.next != cur && p.next.val < cur.val) {
                    p = p.next;
                }
                // 将cur插入到p和p.next之间
                // 因为cur被插到前面，pre的指针需要跳过cur
                pre.next = cur.next;
                cur.next = p.next;
                p.next = cur;
                // 完成插入后，cur回到pre后面
                cur = pre.next;
            }
        }
        return dummy.next;
    }

}
